//----------------------------------------------------------------------------------------------
//	Filename:	KDTreePointCloud.h
//	Author:		Sandro Spina
//	Date:		1/08/2012
//----------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------
#pragma once

#include <boost/shared_ptr.hpp>

#include "Shape/Shape.h"
#include "Shape/VertexFormats.h"
#include "Geometry/BoundingBox.h"
#include "Threading/List.h"
#include "Maths/Random.h"
#include "Shape/TreePointCloud.h"
#include "Shape/Sphere.h"
#include "Geometry/Ray.h"
#include "Material/MaterialGroup.h"

#include <nanoflann.hpp>
#include <Eigen/Dense>

namespace Illumina 
{
	namespace Core
	{		
		//----------------------------------------------------------------------------------------------
		// KD-Tree Node
		//----------------------------------------------------------------------------------------------
		// Represents a single node in the kd-tree structure. Note that only leaf nodes in the 
		// structure contain any geometry.
		//----------------------------------------------------------------------------------------------
		struct KDTreePointCloudNode
		{
			// Node Type
			ITreePointCloud::NodeType Type;

			// Node bounding box
			AxisAlignedBoundingBox BoundingBox;

			// Partition Axis
			int Axis;

			// Partition Point
			float Partition;

			// Only if an internal node
			KDTreePointCloudNode *m_pChild[2];

			// Only if a leaf
			List<int> PointList;			
			
			KDTreePointCloudNode() { m_pChild[0] = m_pChild[1] = NULL; }
			~KDTreePointCloudNode() { }
		};

		//----------------------------------------------------------------------------------------------
		//----------------------------------------------------------------------------------------------
		class KDTreePointCloud 
			: public ITreePointCloud
		{
		protected:
			// Point Cloud area
			float m_fArea;			

			// Uniform random number generator for sampling
			Random m_random;

			KDTreePointCloudNode m_rootNode;	//For Ray intersection and Rendering
			int m_nMaxLeafObjects;
			int m_nMaxTreeDepth;
			float m_fMinNodeWidth;

			Sphere *s;
			Ray *r;			

		public:
			KDTreePointCloud(int p_nMaxObjectsPerLeaf = 10 /*16*/, int p_nMaxTreeDepth = 35 /*30*/);
			KDTreePointCloud(const std::string &p_strName, int p_nMaxObjectsPerLeaf = 10 /*16*/, int p_nMaxTreeDepth = 35 /*30*/);
			~KDTreePointCloud();

			boost::shared_ptr<IPointCloud> CreateInstance(void);

			// Must return the number of data points
			inline size_t kdtree_get_point_count() const { return m_pointList.size(); }			

			// Returns the distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:
			inline float kdtree_distance(const float *p1, const size_t idx_p2,size_t size) const
			{
				const float d0=p1[0]-m_pointList[idx_p2].m_vertex.Position[0];
				const float d1=p1[1]-m_pointList[idx_p2].m_vertex.Position[1];
				const float d2=p1[2]-m_pointList[idx_p2].m_vertex.Position[2];
				return d0*d0+d1*d1+d2*d2;
			}

			// Returns the dim'th component of the idx'th point in the class:
			// Since this is inlined and the "dim" argument is typically an immediate value, the
			//  "if/else's" are actually solved at compile time.
			inline float kdtree_get_pt(const size_t idx, int dim) const
			{
				if (dim==0) return m_pointList[idx].m_vertex.Position[0];
				else if (dim==1) return m_pointList[idx].m_vertex.Position[1];
				else return m_pointList[idx].m_vertex.Position[2];
			}

			template <class BBOX>
			bool kdtree_get_bbox(BBOX &bb) const { return false; }

			// Bounding volume
			bool IsBounded(void) const;									

			// Area methods
			void ComputeArea(void);
			float GetArea(void) const;

			// Normals
			bool UpdateNormals(void);

			// Compile method used to prepare complex structures for usage (e.g., BVHs)
			bool IsCompilationRequired(void) const { return true; }
			bool Compile(void); // { ComputeArea(); return true; }

			// Update and rebuild methods for dynamic meshes
			bool Update(void) { return true; }
			bool Rebuild(void) { return true; }

			//Nearest Neighbour Methods
			bool ComputePointTypes(int p_rangeMin, int p_rangeMax);
			bool ComputeCornerTypes(std::vector<int> &edge_point_indices, bool p_view);
			//bool ViewComputationOfCornerTypes(float p_ballRadius); 

			//Filter Methods
			int DiscardPointsWithType(int p_type, int p_rangeMin, int p_rangeMax);
			bool DiscardPointsWithSegmentId(int p_segment, int p_rangeMin, int p_rangeMax);
			bool DiscardAllButPointsWithSegmentId(int p_segment, int p_rangeMin, int p_rangeMax);
			bool SetVisiblePointsWithTypeId(int p_type);
			bool SetVisiblePointsWithTypeId(int p_type, std::map<int,int> &segments_map);
			bool SetVisiblePointsWithIds(std::vector<int> &p_indices);
			bool SetVisiblePointsWithSegmentId(int p_segment);
			bool SetVisiblePointsWithSegmentIds(std::vector<int> p_segments);
			bool AddToVisiblePointsWithSegmentIds(std::vector<int> p_segments);
			bool SetInvisiblePointsWithSegmentId(int p_segmentId);
			bool SetInvisibleAllPointsExceptForSegmentId(int p_segmentId);
			bool SetVisibleNextPrimitiveInSegment(int p_segmentId, int p_intenralsegmentId);
			bool SetVisibleNonFittedPointsInSegment(int p_segmentId);
			bool SetPointInvisible(int p_point);
			bool SetPointVisible(int p_point);
			bool SetPointNeighbourhoodVisible(int p_point);
			bool SetVisibleAllPointsExceptForSegmentId(int p_segment);
			bool SetVisibleAllPoints();
			bool SetInvisibleAllPoints();
			bool SetInvisibleAllPointsExceptSeeds();
			bool AddNoise(float p_noise, int p_rangeMin, int p_rangeMax);
			void SetAllPointsInOneSegment();		
			void RestoreAllPointsSegmentIdsFromCache();

			// Sampling methods
			float GetPdf(const Vector3 &p_point) const;
			Vector3 SamplePoint(float p_u, float p_v, Vector3 &p_normal);
			Vector3 SamplePoint(const Vector3 &p_viewPoint, float p_u, float p_v, Vector3 &p_normal);

			// Intersect methods
			bool IntersectsTrivial(const Ray &p_ray, DifferentialSurface &p_surface);
			bool IntersectsTrivial(const Ray &p_ray);
			bool Intersects(const Ray &p_ray, DifferentialSurface &p_surface);
			bool Intersects(const Ray &p_ray);
			bool IntersectSphere(const Vector3 &p_rOrigin, const Vector3 &p_rDirection, CloudPoint &p_cloudPoint, float p_rMin, float p_rMax, DifferentialSurface &p_surface);
			bool IntersectSphere(const Vector3 &p_rOrigin, const Vector3 &p_rDirection, Vector3 &p_sCentre, float p_rMin, float p_rMax);
			bool IntersectPlane(const Vector3 &p_rOrigin, const Vector3 &p_rDirection, Vector3 &p_sCentre, float p_rMin, float p_rMax, DifferentialSurface &p_surface);
			bool IntersectPlane(const Vector3 &p_rOrigin, const Vector3 &p_rDirection, Vector3 &p_sCentre, float p_rMin, float p_rMax);

			bool WriteToBKD3File(std::string p_filePath, bool p_blab, MaterialGroup * p_materialGroup);
			bool ReadFromBKD3File(std::string p_filePath);

			std::string ToString(void) const;

		protected:			
			KDTreePointCloudNode* RequestNode(void);
			int ReleaseNode(KDTreePointCloudNode *p_pNode);
			void BuildHierarchy(KDTreePointCloudNode *p_pNode, std::vector<CloudPoint> &p_objectList, int p_nAxis, int p_nDepth = 0);		
			void BuildHierarchy_S2(KDTreePointCloudNode *p_pNode, List<int> &p_objectList, int p_nAxis, int p_nDepth = 0);			
		};		
	} 
}